package 完全二叉树的节点个数;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: zhengtao
 * @description: 完全二叉树的节点个数
 * @version: 1.0
 * @date: 2022/10/30  10:42
 */
public class Demo222 {

     //Definition for a binary tree node.
     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }
    //层次遍历实现
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int count=0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                while (size-->0){
                    TreeNode poll = queue.poll();
                    count++;
                    if(poll.left!=null){
                        queue.add(poll.left);
                    }
                    if(poll.right!=null){
                        queue.add(poll.right);
                    }
                }
            }
        return count;
    }
     //后序遍历实现
    //1.确定函数参数与返回值
    public int countNodes1(TreeNode root) {
         //2.递归终止条件
        if(root==null){
            return 0;
        }
        int left=countNodes1(root.left);    //左
        int right=countNodes1(root.right);  //右
        return left+right+1;   //中
    }


}
